package com.example.result.alogrithm

import java.util.*
import kotlin.math.min

abstract class  Sort{
    abstract fun sort(arr:IntArray,low:Int,high:Int)
    fun isSorted(arr: IntArray,low: Int,high: Int):Boolean{
        var sorted=true
        for(i in low until high){
            if(arr[i]>arr[i+1]){
                println("error info: in ${i} about ${arr[i]} > ${arr[i+1]}")
                sorted=false
                break
            }
        }
        return  sorted
    }
     fun timeOfSort(arr: IntArray,low: Int,high: Int):Long{
         val startTime=System.currentTimeMillis()
         sort(arr,low,high)
         return System.currentTimeMillis()-startTime
     }
}
class  InsertSort:Sort(){
    override fun sort(arr: IntArray, low: Int, high: Int) {
        var tem=0
        for(i in low..high){
            for(j in i-1 downTo low){
                if(arr[j+1]<arr[j]){
                    tem=arr[j+1]
                    arr[j+1]=arr[j]
                    arr[j]=tem
                }else{
                    break
                }
            }
        }
    }
}
class MergeSort:Sort(){
    var threshot=16
    var insertSort=InsertSort()
    override fun sort(arr: IntArray, low: Int, high: Int) {
        var temArr=IntArray(arr.size)
        var i=1
        while(i<high-low){
            var j=low
            while(j<high){
                var mid= min(j+i-1,high)
                var high= min(j+i*2-1,high)
                if(mid==high){
                    break
                }
                if(high-j<threshot){
                    insertSort.sort(arr,j,high)
                }else {
                    merge(arr, j, mid, high, temArr)
                }
                j+=i*2
            }
            i*=2
        }
    }
    fun merge(arr:IntArray,low: Int,mid :Int,high: Int,temArr : IntArray){
        var i=low
        var j=mid+1
        for(k in low..high){
            when{
                j>high ->{
                    temArr[k]=arr[i++]
                }
                i>mid ->{
                    temArr[k]=arr[j++]
                }
                arr[j]<arr[i] ->{
                    temArr[k]=arr[j++]
                }
                else ->{
                    temArr[k]=arr[i++]
                }
            }
        }
        for(k in low..high){
            arr[k]=temArr[k]
        }
    }

}
class  QuickSort:Sort(){
    var random:Random
    var insertSort=InsertSort()
    var threshold=15
    init {
        random= Random()
    }
    override fun sort(arr: IntArray, low: Int, high: Int) {
        if(low>=high){
            return
        }
        if(high-low<=threshold){
            insertSort.sort(arr, low, high)
            return
        }
//        println("${low} ${high}")
        var start=random.nextInt(high-low)+low
        var tem=arr[start]
        arr[start]=arr[low]
        arr[low]=tem
        var i=low+1
        var j=high
        var p=low+1
        var target=arr[low]
        while(i<=j){
            when {
                arr[i]==target -> {
                    tem=arr[i]
                    arr[i]=arr[p]
                    arr[p]=tem
                    i++
                    p++
                }
                arr[i]<target -> {
                    i++
                }
                else -> {
                    tem=arr[j]
                    arr[j]=arr[i]
                    arr[i]=tem
                    j--
                }
            }
        }
        var moveCount=Math.min(p-low,i-p)
        for(k in 0 until moveCount){
            tem=arr[low+k]
            arr[low+k]=arr[i-1-k]
            arr[i-1-k]=tem
        }
        var l=i-p+low
        sort(arr,low,l-1)
        sort(arr,i,high)


    }

}